Convex minimization, a subfield of optimization, studies the problem of minimizing convex functions over convex sets. The convexity property can make optimization in some sense "easier" than the general case - for example, any local optimum must be a global optimum.
Given a real vector space together with a convex, real-valued function
defined on a convex subset of , the problem is to find a point in for which the number is smallest, i.e., a point such that
The convexity of makes the powerful tools of convex analysis applicable: the Hahn–Banach theorem and the theory of subgradients lead to a particularly satisfying theory of necessary and sufficient conditions for optimality, a duality theory generalizing that for linear programming, and effective computational methods.
Convex minimization has applications in a wide range of disciplines, such as automatic control systems, estimation and signal processing, communications and networks, electronic circuit design, data analysis and modeling, statistics (optimal design), and finance. With recent improvements in computing and in optimization theory, convex minimization is nearly as straightforward as linear programming. Many optimization problems can be reformulated as convex minimization problems. For example, the problem of maximizing a concave function f can be re-formulated equivalently as a problem of minimizing the function -f, which is convex.
Contents |
The following statements are true about the convex minimization problem:
These results are used by the theory of convex minimization along with geometric notions from functional analysis such as the Hilbert projection theorem, the separating hyperplane theorem, and Farkas' lemma.
Standard form is the usual and most intuitive form of describing a convex minimization problem. It consists of the following three parts:
A convex minimization problem is thus written as
Note that every equality constraint can be equivalently replaced by a pair of inequality constraints and . Therefore, for theoretical purposes, equality constraints are redundant; however, it can be beneficial to treat them specially in practice.
Following from this fact, it is easy to understand why has to be affine as opposed to merely being convex. If is convex, is convex, but is concave. Therefore, the only way for to be convex is for to be affine.
The following problems are all convex minimization problems, or can be transformed into convex minimizations problems via a change of variables:
Consider a convex minimization problem given in standard form by a cost function and inequality constraints , where . Then the domain is:
The Lagrangian function for the problem is
For each point x in X that minimizes f over X, there exist real numbers λ0, ..., λm, called Lagrange multipliers, that satisfy these conditions simultaneously:
If there exists a "strictly feasible point", i.e., a point z satisfying
then the statement above can be upgraded to assert that λ0=1.
Conversely, if some x in X satisfies 1-3 for scalars λ0, ..., λm with λ0 = 1, then x is certain to minimize f over X.
Convex minimization problems can be solved by the following contemporary methods:[1]
Other methods of interest:
Subgradient methods can be implemented simply and so are widely used.[2]
Besides convex minimization, the field of convex optimization also considers the far more difficult problem of maximizing convex functions:
Solving even close-to-convex problems can be computationally difficult. The problem of minimizing a quadratic multivariate polynomial on a cube is NP-hard.[4] In fact, in the quadratic minimization problem, if the matrix has only one negative eigenvalue, the problem is NP-hard.[5]
Advanced treatments consider convex functions that can attain positive infinity, also; the indicator function of convex analysis is zero for every and positive infinity otherwise.
Extensions of convex functions include pseudo-convex and quasi-convex functions. Partial extensions of the theory of convex analysis and iterative methods for approximately solving non-convex minimization problems occur in the field of generalized convexity ("abstract convex analysis").
Although most general-purpose nonlinear equation solvers such as LSSOL, LOQO, MINOS, and Lancelot work well, many software packages dealing exclusively with convex minimization problems are also available:
|